More Examples

  1. We start with a miscellaneous counting question
    Consider the set of positive integers less than 1000, S={1,2,,999}S=\{1,2, \cdots, 999\}
    How many elements are divisible by
    i) 7, ii) 11, iii) 7 and 11, iv) 7 or 11, v) exactly one of 7 and 11, vi) neither 7 nor 11 ,

(i) 9997=142+57\frac{999}{7} = 142+\frac{5}{7} This means there are 142 multiples 7 in SS

or 9997]=142\left.\mid \frac{999}{7}\right]=142 multiples of 77 in SS

(ii) By the same reasoning, there are 99911=90+911=90\left.\left\lfloor\frac{999}{11}\right\rfloor=\lfloor 90+\frac{9}{11}\right\rfloor=90 multiples of 11 in S\mathrm{S}

iii) If nn is divisible by 7 and 11 , since gcd(7,11)=1gcd(7,11)=1, nn is divisible by 77
Thus 99977=12+7577=12\left\lfloor\frac{999}{77}\right\rfloor=\left\lfloor 12+\frac{75}{77}\right\rfloor=12 multiples of 7 and 11 in SS

iv) To facilitate our counting, let

Nx={ multiples of x in S} N_{x}=\{\text { multiples of } x \text { in } S\}

Then as we have seen above

N7=142,N11=90,N77=12=N7N11 \left|N_{7}\right|=142,\left|N_{11}\right|=90,\left|N_{77}\right|=12=\left|N_{7} \cap N_{11}\right|

Thus the number of multiples of 7 or 11 in SS is

N7N11=N7+N11N7N11=142+9012=220 \begin{aligned} \left|N_{7} \cup N_{11}\right| & =\left|N_{7}\right|+\left|N_{11}\right|-\left|N_{7} \cap N_{11}\right| \\ & =142+90-12=220 \end{aligned}

v) The number of multiples of exactly one of 7 or 11 is the number of multiples of 7 ox 11 menus the number of multiples of 7 and 11 ,

Thus

N7N11=N7N11N7N11=22012=208 \begin{aligned} \mid N_{7}\oplus N_{11} \mid & =\left|N_{7} \cup N_{11}\right|-\left|N_{7} \cap N_{11}\right| \\ & =220-12=208 \end{aligned}

Vi) The numbers in SS that are neither multiples of 7 nor 11
is the size of the complement of N7N11N_{7} \cup N_{11}

ie.,N7N11=sN7N11=999220=779 \begin{aligned} \text{ie.,}\qquad\left|N_{7} \cup N_{11}\right| & =|s|-\left|N_{7} \cup N_{11}\right| \\ & =999-220=779 \end{aligned}

We now turn our attention to an algebraic result with combinatorics applications

We start by considering powers of a binomial

We have

(x+y)2=x2+2xy+y2(x+y)3=x3+3x2y+3xy2+y3(x+y)4=x4+4x3y+6x2y2+4xy3+y4 \begin{aligned} & (x+y)^{2}=x^{2}+2 x y+y^{2} \\ & (x+y)^{3}=x^{3}+3 x^{2} y+3 x y^{2}+y^{3} \\ & (x+y)^{4}=x^{4}+4 x^{3} y+6 x^{2} y^{2}+4 x y^{3}+y^{4} \end{aligned}

A pattern io starting, to emerge. If we consider the coefficients only we see the pattern

Can we guess what (x+y)5(x+y)^{5} will be? Let us confirm our guess

(x+y)5=(x+y)(x+y)4=(x+y)[x4+4x3y+6x2y2+4xy3+y4]=x5+4x4y+6x3y2+4x2y3+xy4+x4y+4x3y2+6x2y3+4xy4+y5=x5+5x4y+10x3y2+10x2y3+5xy4+y5 \begin{aligned} (x+y)^{5}= & (x+y)(x+y)^{4}\\ =&(x+y)\left[x^{4}+4 x^{3} y+6 x^{2} y^{2}+4 x y^{3}+y^{4}\right] \\ = & x^{5}+4 x^{4} y+6 x^{3} y^{2}+4 x^{2} y^{3}+x y^{4} +x^{4} y+4 x^{3} y^{2}+6 x^{2} y^{3}+4 x y^{4}+y^{5} \\ = & x^{5}+5 x^{4} y+10 x^{3} y^{2}+10 x^{2} y^{3}+5 x y^{4}+y^{5} \end{aligned}

Is there a formula for the coefficients of the nth n^{\text {th }} power of the binomial (x+y)n(x+y)^{n} ?

We see that this formula must read the same in both directions,

12113311464115101051 \begin{aligned} 1\quad&2\quad1 \\ 1\quad3&\quad3\quad1 \\ 1\quad4\quad&6\quad4\quad1 \\ 1\quad5\quad10&\quad10\quad5\quad1 \end{aligned}

If we call these coefficients ckn,k=0,1,,nc_{k}^{n}, k=0,1, \cdots, n we need cnkn=cknc_{n-k}^{n}=c_{k}^{n}.

We have already seen such a number sequence and interestingly enough, they are called the binomial coefficients, (nk)\left(\begin{array}{l}n \\ k\end{array}\right)


This has all been the lead up to

The Binomial Theorem

Let x,yx, y be numbers (real ore complex). Let xx be a non-negative integers

Then

(x+y)n=k=0n(nk)xnkyk (x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k}

Proof We will prove this result by induction after we explore it a bit

Exercise 1 Find the coefficient of x4x^{4} in the expansion of (2x3)10(2 x-3)^{10}

Let a=2x,b=3a=2 x, b=-3, then

(2x3)10=(a+b)10=k=010(10k)a10kbk=k=010(10k)(2x)10k(3)k. We want 10k=4 \begin{aligned} (2 x-3)^{10}& =(a+b)^{10}=\sum_{k=0}^{10}\left(\begin{array}{l} 10 \\ k \end{array}\right) a^{10-k} b^{k} \\ & =\sum_{k=0}^{10}\left(\begin{array}{l} 10 \\ k \end{array}\right)(2 x)^{10-k}(-3)^{k} \text {. We want } 10-k=4 \end{aligned}

k=6k=6 : coefficients of x4x^{4} is the coefficients of
(106)(2x)4(3)6=(210)24(3)6x4 \left(\begin{array}{c} 10 \\ 6 \end{array}\right)(2 x)^{4}(-3)^{6}=(210) 2^{4}(-3)^{6} x^{4}

Coefficients of x4x^{4} is 21024(3)6=210×16×729=2,449,440210 \cdot 2^{4} \cdot(-3)^{6}\\=210 \times 16 \times 729\qquad=2,449,440\qquad\checkmark

Exercise Evaluate N=k=0n4k(nk)\displaystyle N=\sum_{k=0}^{n} 4^{k}\left(\begin{array}{l}n \\ k\end{array}\right)

N=k=0n(nk)1nk4k=(1+4)n=5n N=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) 1^{n-k} 4^{k}=(1+4)^{n}=5^{n}

Theorem Let rZ+,nZ+r \in \mathbb{Z}^{+}, n \in \mathbb{Z}^{+}

(1+r)n=k=0nrk(nk) (1+r)^{n}=\sum_{k=0}^{n} r^{k}\left(\begin{array}{l} n \\ k \end{array}\right)

Proof of Binomial Turn

When n=0n=0, we have the trivial case

(x+y)0=1 and k=00(0k)x0kyk=(00)x0y0=1 (x+y)^{0}=1 \text { and } \sum_{k=0}^{0}\left(\begin{array}{l} 0 \\ k \end{array}\right) x^{0-k} y^{k}=\left(\begin{array}{l} 0 \\ 0 \end{array}\right) x^{0} y^{0}=1

by convention (00)=1\left(\begin{array}{l}0 \\ 0\end{array}\right)=1

When n=1n=1,

(x+y)1=x+y and k=01(1k)x1kyk=(10)x1y0+(11)x0y1=x+y. \begin{aligned} (x+y)^{1}=x+y \qquad\text { and }\\ \sum_{k=0}^{1}\left(\begin{array}{l} 1 \\ k \end{array}\right) x^{1-k} y^{k} & =\left(\begin{array}{l} 1 \\ 0 \end{array}\right) x^{1} y^{0}+\left(\begin{array}{l} 1 \\ 1 \end{array}\right) x^{0} y^{1} \\ & =x+y . \end{aligned}

also a trivia case

When x=2x=2

(x+y)2=x2+2xy+y2+k=02(2k)x2kyk=(20)x2y0+(20)x1y1+(22)x0y2=x2+2xy+y2 \begin{aligned} (x+y)^{2}=x^{2}+2 x y+y^{2} & +\sum_{k=0}^{2}\left(\begin{array}{l} 2 \\ k \end{array}\right) x^{2-k} y^{k} \\ & =\left(\begin{array}{l} 2 \\ 0 \end{array}\right) x^{2} y^{0}+\left(\begin{array}{l} 2 \\ 0 \end{array}\right) x^{1} y^{1}+\left(\begin{array}{l} 2 \\ 2 \end{array}\right) x^{0} y^{2} \\ & =x^{2}+2 x y+y^{2} \end{aligned}

If we let P(n)P(n) be the propositional function given by (1) above,
we have shown that P(0)P(1)P(2)P(0) \wedge P(1)\wedge P(2) is True.

Assume now that P(n)P(n) is tue. Let us ty to prove that P(n+1)P(n+1) is also true.

Now P(x)P(x) the given

(x+y)n+1=(x+y)(x+y)n=(x+y)k=0n(nk)xnkyk=x[xn+k=1n(nk)xnkyk]+y[k=0n1(nk)xnkyk+yn] \begin{aligned} (x+y)^{n+1} & =(x+y)(x+y)^{n}=(x+y) \sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k} \\ & =x\left[x^{n}+\sum_{k=1}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k}\right]+y\left[\sum_{k=0}^{n-1}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k}+y^{n}\right] \end{aligned} =xn+1+k=1n(nk)xn+1kyk+k=0n1(nk)xnkyk+1+yn+1 =x^{n+1}+\sum_{k=1}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n+1-k} y^{k}+\sum_{k=0}^{n-1}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k+1}+y^{n+1}

In the second sum, we change the index form kk to ll by the shift k=l1k=l-1.

then k+1=lk+1=l and k=0l=1,k=n1l=nk=0 \Rightarrow l=1, k=n-1 \Rightarrow l=n

Thus

(x+y)n+1=xn+1+k=1n(nk)xn+1kyk+l=1n(nl1)xn+1lyl+yn+1=xn+1k=1n[(nk)+(nk1)]xn+1kyk+yn+1 \begin{aligned} (x+y)^{n+1} & =x^{n+1}+\sum_{k=1}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n+1-k} y^{k}+\sum_{l=1}^{n}\left(\begin{array}{l} n \\ l-1 \end{array}\right) x^{n+1-l} y^{l}+y^{n+1} \\ & =x^{n+1} \sum^n_{k=1} \left[\left(\begin{array}{l} n \\ k \end{array}\right)+\left(\begin{array}{c} n \\ k-1 \end{array}\right)\right] x^{n+1-k} y^{k}+y^{n+1} \end{aligned}

where we change ll back to kk by l=kl=k in the second sum


Lemma If k+xk+x are positive integers and knk \leq n then

(nk)+(nk1)=(n+1k) \left(\begin{array}{l} n \\ k \end{array}\right)+\left(\begin{array}{c} n \\ k-1 \end{array}\right)=\left(\begin{array}{c} n+1 \\ k \end{array}\right)

(Te prof of the lemma is strictly algebra, given the definition of the binomial coefficients)
(a combinatorial proof is also possible) Applying the lemma we have

(x+y)n+1=xn+1+k=1n(n+1k)xn+1kyk+yk+1=k=0n+1(n+1k)xn+1kyk and P(n+1) \begin{aligned} (x+y)^{n+1} & =x^{n+1}+\sum_{k=1}^{n}\left(\begin{array}{c} n+1 \\ k \end{array}\right) x^{n+1-k} y^{k}+y^{k+1} \\ & =\sum_{k=0}^{n+1}\left(\begin{array}{c} n+1 \\ k \end{array}\right) x^{n+1-k} y^{k} \text { and } P(n+1) \end{aligned}

is tue.

Thus the Binomial Theorem is proved by PMI

Note The lemma is the "Theory" behind Pascal's triangle that quickly gives the binomial coefficients

Starting at the top with a single 1, in what we call now 0 , corresponding to x=0x=0, we build the sows 1,2,3,1,2,3, \cdots that correspond to x=1,33,x=1,33, \cdots, using the lemma.

n=01n=111n=2121n=31331n=414641x=515101051=25n=61615201561n=7172135352171n=818285670562881=28 \begin{aligned} & n=0 & &1& \\ & n=1 & 1&\quad 1& \\ & n=2 & 1 \quad &2 \quad 1& \\ & n=3 & 1 \quad 3& \quad 3 \quad 1& \\ & n=4 & \quad 1 \quad 4 \quad &6 \quad 4 \quad 1&\\ & x=5 & 1 \quad 5 \quad 10& \quad 10 \quad 5 \quad 1&\rightarrow \sum=2^{5}\\ & n=6 & \quad 1 \quad 6 \quad 15 \quad &20 \quad 15 \quad 6 \quad 1& \\ & n=7 & \quad 1 \quad 7 \quad 21 \quad 35& \quad 35 \quad 21 \quad 7 \quad 1& \\ & n=8 & \quad1\quad8\quad28\quad56\quad&70\quad56\quad28\quad8\quad1&\to\sum=2^{8}\\ \end{aligned}

Thus (x+1)7=x7+7x6+21x5+35x4+35x3+21x2+7x+1(x+1)^{7}=x^{7}+7 x^{6}+21 x^{5}+35 x^{4}+35 x^{3}+21 x^{2}+7 x+1


Exercise 1 Find the coefficient of x3y4x^{3} y^{4} in the expansion of (3x4y)10(3 x-4 y)^{10}

Solution Note in the binomial theorem, the powers of the variables add up to the exponent of the binomial
3+4=73+4=7 so there is no term with, x3y4x^{3} y^{4} in it
\therefore\quad It's coefficient is zero!


Exercise 2 Consider (x+1x)10\left(x+\frac{1}{x}\right)^{10}
What is the constant term in it's expansion
(the term with no xx's in it)

(x+1x)10=k=010(10k)x10k(1x)k \left(x+\frac{1}{x}\right)^{10}=\sum_{k=0}^{10}\left(\begin{array}{c} 10 \\ k \end{array}\right) x^{10-k}\left(\frac{1}{x}\right)^{k}

Need xx's to cancel. If we take k=5k=5 we have

(105)x105(1x)5=(105)x5x5=(105) The constant term is (105)=1029876254321=9×7×4=252 \left(\begin{array}{c} 10 \\ 5 \end{array}\right) x^{10-5}\left(\frac{1}{x}\right)^{5}=\left(\begin{array}{c} 10 \\ 5 \end{array}\right) x^{5} \cdot x^{-5}=\left(\begin{array}{c} 10 \\ 5 \end{array}\right) \\[2em] \therefore\text{ The constant term is } \left(\begin{array}{c}10 \\ 5\end{array}\right)= \frac{_{\cancel{10}}^2 \cdot 9 \cdot \cancel{8} \cdot 7 \cdot _{\cancel{6}}^2} { \cancel{5}\cdot \cancel{4}\cdot \cancel{3} \cdot \cancel{2} \cdot 1}\\ =9 \times 7 \times 4=252

Some notes on the Binomial Theorem

(x+y)n=k=0n(nk)xnkyk,n0,nZ (x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k} \quad, n \geqslant 0,\quad n \in \mathbb{Z}
  1. The coefficients (nk)\left(\begin{array}{l}n \\ k\end{array}\right)
    == number of ways to pick k from nn
    == number of subsets of size kk in a set with nn elements

This leads to some interesting results about sets

We can conclude P(S)=2S|P(S)|=2^{|S|} since

(1+1)n=2n=k=0n(nk)= total number of subsets of S (including ,k=0,S,k=n) \begin{aligned} (1+1)^{n}&=2^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right)\\ &=\text { total number of subsets of $S$ (including $\emptyset, k=0, S, k=n$)} \\ \end{aligned}

Also (11)n=0n=0=k=0n(1)k(nk)=k even(nk)k odd(nk)\displaystyle(1-1)^{n}=0^{n}=0=\sum_{k=0}^{n}(-1)^{k}\left(\begin{array}{l}n \\ k\end{array}\right) =\sum_{k \text{ even}}\left(\begin{array}{l} n \\ k \end{array}\right)-\sum_{k \text{ odd}}\left(\begin{array}{l} n \\ k \end{array}\right)

\therefore The total number of subsets of SS with even number of element = total number of subsets of SS with odd number of elements


Back to counting problems

So far we have discussed permutation and combinations of distinguishable objects

We now consider permutation and combinations of indistinguishable objects

We are given a list of different types of object from which we may select repeatedly from any or all of the types

Permutations with Repetition

Suppose we have a set with nn elements. Recall that the number of ways to permute rr of these elements is

P(n,r)=n(n1)(nr+1)=n!(nr)! P(n, r)=n(n-1) \cdots(n-r+1)=\frac{n !}{(n-r) !}

This is the number of different ways to take rr objects out of nn, where order counts

Permutation with Repetition or Permutation with replacement is the number of ways to "indicate" rr objects out of nn where order count

Think of it as "catch and release"

We have nn ways to pick the first object, which we record on a list, and then put back into the pool of eligible choices, and then we still have nn choices for the second objet, and so on

Thus

 numberr-permutations with repetition =nr \text { numberr-permutations with repetition }=n^{r}

Example How many strings of length nn can be made from the english alphabet?

Answer: 26x26^{x}


The equivalent type of formulation to "catch and release" for repetition pwblems is to assume that the rr different objects being chosen from are nn different types of objects with enough of each type to satisfy the conditions imposed


Combinations with Repetition

Consider the "donut" problem

We go to a donut shop to buy 6 donuts. There are 9 types of donuts to choose from
Assuming there are at least 6 of each type,
how many different ways cen we fill the order?

Since the order in which we pick the donuts does not matter to the finial outcome we can picture the situation as follows

Suppose we take out box has nine compartments, one for each type of donuts
This means there are 8=918=9-1 internal dividers

We now put the 6 donuts in a line inside the box, so that we have a now of 8+6=148+6=14 objects, donuts is one type and dividers is the other type

Let a bar, \mid, represent a divider and a star, *, represent a donut

A choice of donuts then is represented by a string of stars and bars,

Forexample

{} \{\mid |* * \mid * \mid * \mid | * * \mid|\}

represents the following choice

Type 1 2 3 4 5 6 7 8 9
Number of that type 0 0 2 1 1 0 2 0 0

Equivalently a choice of donuts is represented by a bit sting of length
14=(91)+614=(9-1)+6 with 6 zeros in it

There are (146)\left(\begin{array}{c} 14 \\ 6 \end{array}\right) bit strings of length 14 with exactly 6 zeros in it

Thus there are

(146)=147131211110193654321=713113=3003 \left(\begin{array}{c} 14 \\ 6 \end{array}\right)=\frac{_{\cancel{14}}^7 \cdot 13 \cdot _{\cancel{12}}^1 \cdot 11 \cdot _{\cancel{10}}^1 \cdot _{\cancel{9}}^{3}} {\cancel{6} \cdot \cancel{5} \cdot \cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot 1} =7 \cdot 13 \cdot 11 \cdot 3=3003

different orders of 6 donuts from 9 types.

Theorem The number of ways to choose rr object from nn different types of objects is

(n1+rr) \left(\begin{array}{c} n-1+r \\ r \end{array}\right)

Example

  1. How many solutions are there to x1+x2+x3=11x_{1}+x_{2}+x_{3}=11 where x1,x2,x3x_{1}, x_{2}, x_{3} non-negative integers?

This is the number of ways to select 11 objects from 3 types of objects, types x1,x2,x3x_{1}, x_{2}, x_{3}.

That is (31+1111)=(1311)=(132)=13,1221=78\left(\begin{array}{c}3-1+11 \\ 11\end{array}\right)=\left(\begin{array}{l}13 \\ 11\end{array}\right)=\left(\begin{array}{l}13 \\ 2\end{array}\right)=\frac{13,12}{2 \cdot 1}=78

Example 2 How many solutions are there to x1+x2+x3=11x_{1}+x_{2}+x_{3}=11 if x1,x2,x3x_{1}, x_{2}, x_{3} are nonnegative integers and x1,x21,x32x_{1},\quad x_{2} \geqslant 1,\quad x_{3} \geqslant 2 ?

We fist pick
1 of type x1x_{1}
1 of type x2x_{2}
2 of type x3x_{3}

then we require that

x1+x2+x3=7 for our remaining solution  x_{1}+x_{2}+x_{3}=7 \qquad\text { for our remaining solution }

and x1,x2,x30x_{1}, x_{2}, x_{3} \geqslant 0,

This can be done in

(31+77)=(97)=(92)=982.1=36 ways  \left(\begin{array}{c} 3-1+7 \\ 7 \end{array}\right)=\left(\begin{array}{l} 9 \\ 7 \end{array}\right)=\left(\begin{array}{l} 9 \\ 2 \end{array}\right)=\frac{9 \cdot 8}{2.1}=36 \text { ways }

Permutations with Indistinguishable Objects

Let us consider the number of different strings that can he made from the letters of the word

SUCCESS \operatorname{SUCCESS}

There are 4 different letters to choose from

S3 of themU1 of themC2 of themE1 of them \begin{aligned} & S \rightarrow 3 \textsf { of them} \\ & U \rightarrow 1 \textsf { of them} \\ & C \rightarrow 2 \textsf { of them} \\ & E \rightarrow 1 \textsf { of them} \end{aligned}

Exercise How many solutions are there to
x1+x2+x3=11x_{1}+x_{2}+x_{3}=11 where x1,x20x_{1}, x_{2} \geqslant 0 and 0x320 \leq x_{3} \leq 2 ?

Solution 3 cases to consider

Case i) x3=0x_{3}=0, have x1+x2=11x_{1}+x_{2}=11

number of solutions (21+1111)=(1211)=12\left(\begin{array}{c}2-1+11 \\ 11\end{array}\right)=\left(\begin{array}{l}12 \\ 11\end{array}\right)=12

Case ii) x3=1x_{3}=1, have x1+x2=10x_{1}+x_{2}=10

number of solutions (21+1010)=(1110)=11\left(\begin{array}{c}2-1+10 \\ 10\end{array}\right)=\left(\begin{array}{l}11 \\ 10\end{array}\right)=11

case iii) x3=2,x1+x2=9x_{3}=2, x_{1}+x_{2}=9

number of sins (21+99)=(109)=10\left(\begin{array}{c}2-1+9 \\ 9\end{array}\right)=\left(\begin{array}{c}10 \\ 9\end{array}\right)=10

\therefore Total number of solutions is 10+11+12=33 10+11+12=33

We have a total of 7 letters to permute and this can be done in 7!7! ways. However, there are 3 copies of the letter SS that are indistinguishable from each other

There one 3!=63 !=6 ways to permute 3 objects and so each specific rearrangement of SUCCESSSUCCESS is got in 3!3! ways

To see this think of the SS's as labelled S1UCCES2S3 S_{1} U C C E S_{2} S_{3}

Then the rearrangement S2UCCES1S3S_{2} U C C E S_{1} S_{3} is the same word as are

S2UCCES3S1S1UCCES3S2S3UCCES1S2S3UCCES2S1 \begin{aligned} & S_{2} U C C E S_{3} S_{1} \\ & S_{1} U C C E S_{3} S_{2} \\ & S_{3} U C C E S_{1} S_{2} \\ & S_{3} U C C E S_{2} S_{1} \end{aligned}

Also, each one of these rearrangements have 2!2! duplications to account for the 2 letter CC's

eg SUC1C2ES5S U C_{1} C_{2} E S 5 and SUC2C1ESSS U C_{2} C_{1} E S S are permutations of the letters that give us the same word,

Thus there are 7!3!2!=7×6×5×4×3×2×13×2×12×1=420 different 7 letter words obtainable from the letters in SUCCESS \displaystyle \frac{7!}{3!2!}=\frac{7\times\cancel{6}\times5\times4\times3\times\cancel{2}\times\cancel{1}}{3\times2\times1\quad2\times1}\\[1em] =420 \text { different } 7 \text { letter words obtainable from the letters in SUCCESS }


Theorem Let nn objects of kk different types, where there are nin_{i} of type i,i=1,,k(n=i=1kni)\displaystyle i,\\[1em] i=1, \cdots, k\left(n=\sum_{i=1}^{k} n_{i}\right), be permuted. Then there are

n!n1!n2!nk!\displaystyle \frac{n !}{n_{1} ! n_{2} ! \cdots n_{k} !} different results


Example Consider the word AARDVARK.

  1. How many different 8 letter words can be made from its letters?
  2. How many different 8 letter words can be made from its letters if the 3 A's must occur consecutively?

Solution

 1) We have A3D1R2V1K1 number of ways =8!3!1!2!1!1!=8765432132121=3360 ways  \begin{gathered} \begin{aligned} \text { 1) We have } A & \rightarrow 3 \\ D & \rightarrow 1 \\ R & \rightarrow 2 \\ V & \rightarrow 1 \\ K & \rightarrow 1 \end{aligned} \\ \text { number of ways }=\frac{8 !}{3 ! 1 ! 2 ! 1 ! 1 !}=\frac{8 \cdot 7 \cdot \cancel{6} \cdot 5 \cdot 4 \cdot 3 \cdot \cancel{2} \cdot \cancel{1}}{\cancel{3}\cdot\cancel{2} \cdot \cancel{1} \cdot 2 \cdot 1}=3360 \text { ways } \end{gathered}
  1. If we have all 3 A's consecutive then we must permute the 6 letters
AAA1D1R2V1K1 number of ways =6!2!=6.5.4.3=360 ways.  \begin{gathered} A A A \rightarrow 1 \\ D \rightarrow 1 \\ R \rightarrow 2 \\ V \rightarrow 1 \\ K \rightarrow 1 \\ \text { number of ways }=\frac{6 !}{2 !}=6.5 .4 .3=360 \text { ways. } \end{gathered}

Distributing objects into boxes

Suppose we have nn different objects (distinguishable) that we wish to put into kk distinguishable boxes such that nin_{i} objects go into box.

We will count the number of ways to do this by showing a 111-1 correspondence to the permutation of nn objects with kk types of indistinguishable objects, each with nin_{i} objects, i=1,,ki=1, \cdots, k_{\text {. }}

List the object 1,2,,n1,2, \cdots, n. List the boxes, B1,B2,,BRB_{1}, B_{2}, \cdots, B_{R} Assign to each number l,1lnl, 1 \leq l \leq n, the letter of the box it goes into to get a sequence of letters Bi1Bi2Bin B_{i_{1}} B_{i_{2}} \cdots B_{i_{n}}\leftarrow some of these can be the same letter

Every assignment of objects to boxes thus corresponds to one and only one permutation of nn objects of kk different types with nin_{i} of each type, i=1,,ki=1, \cdots, k.

Since two sets have the same cardinality if there is a 111-1 correspondence between them, we have

Theorem The number of ways to distribute nn distinguishable objects into kk distinguishable boxes so that nin_{i} are placed in box i,i=1,,ki,\quad i=1, \cdots, k, is

n!n1!n2!nk! \frac{n !}{n_{1} ! n_{2} ! \cdots n_{k} !}

Note If can be argued, as well, that we have (nn1)\left(\begin{array}{l}n \\ n_{1}\end{array}\right) ways to put n1n_{1}, items in box 1, then (nn1n2)\left(\begin{array}{c}n-n_{1} \\ n_{2}\end{array}\right) ways to put n2n_{2} items in box 2, then (nn1n2n3)\left(\begin{array}{c}n-n_{1}-n_{2} \\ n_{3}\end{array}\right) ways to put nn, items in box 3, \cdots, finally (nn1n2nk1nk)=(nknk)=1\left(\begin{array}{c}n-n_{1}-n_{2}-\cdots-n_{k-1} \\ n_{k}\end{array}\right)=\left(\begin{array}{l}n_{k} \\ n_{k}\end{array}\right)=1 ways to put nkn_{k} items in box k(n=n1++nk)k\left(n=n_{1}+\cdots+n_{k}\right) and thus

Theorem

If n=n1+n2++nkn=n_{1}+n_{2}+\cdots+n_{k},

(nn1)(nn1n2)(nn1n2n3)(nn1nk1nk)=n!n1!n2!nk! \begin{gathered} \left(\begin{array}{l} n \\ n_{1} \end{array}\right) \cdot\left(\begin{array}{c} n-n_{1} \\ n_{2} \end{array}\right)\left(\begin{array}{c} n-n_{1}-n_{2} \\ n_{3} \end{array}\right) \cdots\left(\begin{array}{c} n-n_{1}-\cdots-n_{k-1} \\ n_{k} \end{array}\right) \\ =\frac{n !}{n_{1} ! n_{2} ! \cdots n_{k} !} \end{gathered}

Examples

  1. How many ways can 5 cards be dealt to 5 players from a standard card deck?

Solution There are 6 boxes, 5 get 5 cards (dealt cards) and 1 box gets 525×5=5225=2752-5 \times 5=52-25=27 cards (undealt cards)

 number of way =52!(5!)527!= a really big number =2.976866584×1029 \begin{aligned} \text { number of way }=\frac{52 !}{(5 !)^{5} 27 !} & =\text { a really big number } \\ & =2.976866584 \times 10^{29} \end{aligned}
  1. How many different bridge deals are there?

Solution In bridge, the 52 cards are dealt equally to 4 hands, 13 in each, so

 number of ways =52!(13!)45.4×1028 \text { number of ways }=\frac{52 !}{(13 !)^{4}} \approx 5.4 \times 10^{28}
  1. How many bridge deals have all cards from one suit in one player's
    hand?

Solution First pick a suit. This can be done in (41)=4\left(\begin{array}{c} 4 \\ 1 \end{array}\right)=4 ways

Now take all of those cards and put them in one hand

Now deal the other 39 cards to 3 hands in

39!(13!)3 ways.  \frac{39!}{(13!)^{3}} \text { ways. }

thus the total number of ways is

439!(13!)3 4\cdot \frac{39 !}{(13!)^{3}}

Note If we take the ratio of the answers to 3 and 2, We get the probability that bridge hand will come up with one player getting all 3 cards in his hand from one suit

 Probability =439!(13!)3×(13!)452!=4×39!×13!52!=1158,753,389,900 \begin{aligned} & \text { Probability }=4 \cdot \frac{39 !}{(13 !)^{3}} \times \frac{(13 !)^{4}}{52 !}=\frac{4 \times 39 ! \times 13 !}{52 !} \\ & =\frac{1}{158,753,389,900} \\ \end{aligned} §6.4P443#19,12§6,5P454#19,1416,3137 \begin{aligned} \S &6.4 \quad P 443 \quad \# 1-9,12 \\ \S &6,5 \quad P 454 \quad \# 1-9,14-16,31-37 \end{aligned}

APPENDIX 1

Recall the general definition tor the binomial coefficients that was valid for any real number in the top spot

Let αR\alpha \in \mathbb{R}, then

(αk)=α(α1)(αk+1)k! \left(\begin{array}{l} \alpha \\ k \end{array}\right)=\frac{\alpha(\alpha-1) \cdots(\alpha-k+1)}{k !} \text {. }

Generalized Binomial Theorem

Let xR,x<1x \in \mathbb{R},|x|<1. Let αR\alpha \in \mathbb{R}. Then

(1+x)α=k=0+(αk)xk (1+x)^{\alpha}=\sum_{k=0}^{+\infty}\left(\begin{array}{l} \alpha \\ k \end{array}\right) x^{k}

The proof of this result is beyond the scope of this course

We give a few examples of the first few terms of some standard expansions

(1+x)12=k=0+(1/2k)xk=1+1/21!x+(1/2)(1/2)(3/2)3!x3+\displaystyle(1+x)^{\frac{1}{2}}=\sum^{+\infty}_{k=0}\left(\begin{array}{c} 1/2 \\ k \end{array}\right)x^k = 1 + \frac{1/2}{1!}x + \frac{(1/2)(-1/2)(-3/2)}{3!}x^3+\cdots

ie 1+x=1+x2x28+x316\displaystyle \sqrt{1+x}=1+\frac{x}{2}-\frac{x^2}{8}+\frac{x^3}{16}-\cdots

(1+x)12=k=0+(1/2k)xk=1+x2x28x316,x<1\displaystyle(1+x)^{-\frac{1}{2}}=\sum^{+\infty}_{k=0}\left(\begin{array}{c} -1/2 \\ k \end{array}\right)x^k = 1 + \frac{x}{2} - \frac{x^2}{8} - \frac{x^3}{16} -\cdots \quad ,\left| x \right|\lt 1

Course Recap

Counting

Special cases and Results

  1. number of functions from AA to B,A,BB, A, B finite sets
  2. Applications of inc. Excl. Rule
  3. Tree Diagrams
  4. Pigeon Hole Principle a Generalized P. H.P.
  5. Permutations (oder counts) P(n,r)P(n, r)
  6. Combinations (oder doesn't count) C(n,r)=(nr)C(n, r)=\left(\begin{array}{l}n \\ r\end{array}\right)
  7. Binomial Theorem, Binomial Coefficients, (nr)\left(\begin{array}{l}n \\ r\end{array}\right) and Applications
  8. Pascal' Triangle
  9. Generalized Binomial theorem extra
  10. Permutations with repetitions
  11. Combinations with repetitions
  12. Permutations with indistinguishable Objects
  13. Distinguishable items in boxes